package top.humbleyuan.divide_conquer;


import java.util.Arrays;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 15:54
 * @Des 柱状图中最大矩形
 */
public class LeetCode_84 {

    /**
     * 分治法
     */
    public static void main(String[] args) {
        /**
         * 最大矩形出现的三种情况：
         * 1. 以最矮矩形为高的矩形
         * 2. 最矮矩形左边的部分中有最大
         * 3. 最矮矩形右边的部分中有最大
         * 其中2，3中找最大依然按照这种方式
         */

        int[] heights = {2,1,5,6,2,3};

        int max = divide(heights, 0);
        System.out.println(max);
    }

    public static int divide(int[] heights, int maxArea) {
        if(heights == null || heights.length == 0) {
            return maxArea;
        }

        int minHeight = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int i = 0; i < heights.length; i++) {
            if(heights[i] < minHeight) {
                minIndex = i;
                minHeight = heights[i];
            }
        }

        maxArea = Math.max(maxArea, minHeight * heights.length);

        // 左右开弓
        int[] left = Arrays.copyOf(heights, minIndex);
        int[] right = Arrays.copyOfRange(heights, minIndex + 1, heights.length);

        maxArea = Math.max(maxArea, Math.max(divide(left, maxArea), divide(right, maxArea)));

        return maxArea;

    }


}
